import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86183
 * Date: 2022-10-27
 * Time: 9:27
 */
public class Test {
    public static void main(String[] args) {
        int[]  array = {29,5,6,89,2,4,1,56};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }

    private static void quickSort(int[] array) {
        quick(array,0,array.length-1);
    }

    private static void quick(int[] array, int left, int right) {
        if(left >= right){
            return;
        }
//        int pivot = Hoare(array,left,right);
        int pivot = Hoare1(array,left,right);
        quick(array,left,pivot-1);
        quick(array,pivot+1,right);
    }

    /**
     * 挖坑法
     * @param array
     * @param left
     * @param right
     */
    private static int Hoare1(int[] array, int left, int right) {
        int pivot = array[left];
        while (left < right){
            while (left < right && array[right] >= pivot ){
                right --;
            }
            array[left] = array[right];
            while (left < right && array[left] <= pivot){
                left ++;
            }
            array[right] = array[left];
        }
        array[left] = pivot;
        return left;

    }

    /**
     * Hoare法
     * @param array
     * @param left
     * @param right
     * @return
     */
    private static int Hoare(int[] array, int left, int right) {
        int i = left;
        int pivot = array[left];
        while (left < right){
            while (left < right && array[right] >= pivot){
                right--;
            }
            while (left < right && array[left] <= pivot){
                left ++;
            }
            swap (array,left,right);
        }
        swap(array,left,i);
        return left;
    }


    private static void swap(int[] array, int left, int right) {
        int tmp = array[left];
        array[left] = array[right];
        array[right] = tmp;
    }
}
